package oj.oj_150;
//逆波兰表达式求值
//https://leetcode.cn/problems/evaluate-reverse-polish-notation/
import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public int evalRPN(String[] tokens) {
        // 定义栈
        // 栈里保存操作数，int / long，建议在 OJ 题中，能使用 long 就用 long
        // 使用 long 的包装类 Long
        Deque<Long> stack = new LinkedList<>();

        // 遍历每个 token
        for (String token : tokens) {
            // 判断 token 是操作数还是操作符
            if (!isOperator(token)) {
                // 不是操作符，所以是操作数
                // 先把 String 转换成 long
                long n = Long.parseLong(token);
                // 把操作数压入栈
                stack.push(n);
            } else {
                // 因为 + - * / 都是二元运算符
                // 直接从栈中弹出两个操作数
                // 注意，n1 + n2，先弹出 n2，后弹出 n1
                long n2 = stack.pop();
                long n1 = stack.pop();
                // 根据不同的操作符，进行计算
                long r = calc(n1, n2, token);
                // 计算完成之后，再把结果压入栈
                stack.push(r);
            }
        }

        // 结果就是栈顶这个元素
        Long e = stack.pop();
        long r = e.longValue();
        return (int)r;
    }

    // 进行计算
    private long calc(long n1, long n2, String op) {
        // Java 中的 swtich case 是支持 String 类型的
        switch (op) {
            case "+": return n1 + n2;
            case "-": return n1 - n2;   // 前后顺序很重要
            case "*": return n1 * n2;
            case "/": return n1 / n2;   // 前后顺序很重要
            default: return -1;         // 这里是不可能走到的
        }
    }

    // 判断是不是操作符
    private boolean isOperator(String s) {
        // String 比较一定要用 equals
        if (s.equals("+")) {
            return true;
        }

        if (s.equals("-")) {
            return true;
        }

        if (s.equals("*")) {
            return true;
        }

        return s.equals("/");
    }
}
